Moving kNN query processing in metric space based on influential sets

Abstract

The moving k nearest neighbor query computes one's k nearest neighbor set and maintains it while at move. This query is gaining importance due to the prevalent use of smart mobile devices and location-based services. Safe region is a popular technique for processing the query. It is a region where the movement of the query object does not cause the query answer to change. Processing a moving k nearest neighbor query is a continuing process of validating the safe region and recomputing it if invalidated. The size of the safe region largely decides the recomputation frequency and hence query efficiency. Existing algorithms lack efficiency due to either computing too small safe regions frequent..